import java.util.Map;
import java.util.TreeMap;

/**
 * 715. Range 模块
 * https://leetcode-cn.com/problems/range-module/
 */
public class Solutions_715 {
    public static void main(String[] args) {
        RangeModule obj = new RangeModule();
        obj.addRange(7, 15);
        obj.addRange(10, 20);
        obj.addRange(12, 21);
        obj.addRange(30, 88);
        boolean res1 = obj.queryRange(50, 60);  // output: true
        System.out.println(res1);
        obj.removeRange(14, 57);
        boolean res2 = obj.queryRange(10, 14);  // output: true
        System.out.println(res2);
        boolean res3 = obj.queryRange(13, 15);  // output: false
        System.out.println(res3);
        boolean res4 = obj.queryRange(16, 17);  // output: false
        System.out.println(res4);
        boolean res5 = obj.queryRange(50, 60);  // output: false
        System.out.println(res5);
        boolean res6 = obj.queryRange(77, 88);  // output: true
        System.out.println(res6);

//        obj.addRange(5, 6);
//        obj.addRange(2, 8);
//        boolean res1 = obj.queryRange(1, 4);  // output: false
//        obj.removeRange(2, 4);
//        boolean res2 = obj.queryRange(4, 5);  // output: true
//        obj.removeRange(4, 6);
//        obj.addRange(5, 9);
//        boolean res3 = obj.queryRange(5, 6);  // output: true
//        obj.removeRange(6, 7);
    }
}

class RangeModule {
    // 使用 treeMap 来记录区间
    // {10, 20}，表示已记录区间 [10, 20)
    TreeMap<Integer, Integer> treeMap = null;

    public RangeModule() {
        treeMap = new TreeMap<>();
    }

    public void addRange(int left, int right) {
        while (true) {
            // 对 treeMap 中与 [left, right) 区间重叠的区间进行合并的操作
            // 即开始索引小于等于 right 并且结束索引大于 left 的区间、
            // 如 [7, 15) 与 [10, 20) 就需要合并，因为 7 小于 20，且 15 大于 10
            // 如 [7, 15) 与 [15, 20) 也需要合并，因为 7 小于 15，且 15 大于等于 15
            Map.Entry<Integer, Integer> entry = treeMap.floorEntry(right);
            // 关键：entry.getValue() >= left，需要用大于等于，而不是等于
            if (entry != null && entry.getValue() >= left) {
                int key = entry.getKey(), value = entry.getValue();

                // 合并区间
                left = Math.min(left, key);
                right = Math.max(right, value);
                // 删除区间
                treeMap.remove(key);
            } else {
                break;
            }
        }
        treeMap.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        // 获取到小于等于 left 的最大键
        Map.Entry<Integer, Integer> entry = treeMap.floorEntry(left);
        if (entry != null && entry.getValue() >= right) {
            return true;
        }
        return false;
    }

    // 若 treeMap 中有 [7, 21)，[30, 88) 区间
    // 现有删除区间 left, right = [14, 57)，删除后，最终 treeMap 中还有 [7, 14)，[57, 88)
    public void removeRange(int left, int right) {
        // 查找末尾索引 > left 的区间，即 [7, 21)
        Map.Entry<Integer, Integer> entry = treeMap.floorEntry(left);
        if (entry != null && entry.getValue() > left) {
            int key = entry.getKey(), value = entry.getValue();
            treeMap.remove(key);
            if (key < left) {
                // 前半段
                treeMap.put(key, left);
            }
            if (value > right) {
                // 后半段
                treeMap.put(right, value);
            }
        }
        // 查找开始索引 < right 的区间，即 [30, 88)
        while (true) {
            Map.Entry<Integer, Integer> entry1 = treeMap.ceilingEntry(left);
            if (entry1 != null && entry1.getKey() < right) {
                int key = entry1.getKey(), value = entry1.getValue();
                // 区间删除
                treeMap.remove(key);
                if (value > right) {
                    // 将剩余区间部分，继续存储
                    treeMap.put(right, value);
                }
            } else {
                break;
            }
        }
    }
}


